This invention relates to a detection system for determining information concerning the location of objects. The invention can be applied to people and animals as well as inanimate objects such a furniture, machines, vehicles, equipment and the like, and in this connection object is intended to include any movable entity.
Location systems are known which allow the presence or absence of an object in a specified environment (such as a room) to be confirmed or denied, and relative to one or more reference points to identify where in the environment the object is located.
EP 0485879 describes a system for locating vehicles in automatic guidance transport systems. Ultrasound is employed as a distance measuring medium whilst an infra-red link allows communication between vehicles.
WO95/14241 describes a tracking system which enables a spotlight to follow a person on a stage carrying a transponder. Again infra-red signals are used to instigate ultrasonic transmissions to determine the position of the transponder and therefore the person. The spotlight is moved accordingly.
EP 0591899 describes another spotlight controlling system for tracking a moving target (actor on a stage) carrying a transponder. Here radio transmissions establish the communication link and ultrasound transmissions are employed to determine distance and position.
In our UK Patent Applications Nos. 9725760.4, 9725718.2 and 9725759.6, there is described an indoor positioning system wherein a single radio transmitter (part of a zone manager) transmits 25 radio signals each second, at the start of a 40 ms interval called a timeslot.
The radio signals, which are picked up by mobile transmitter/receivers (transponders) in rooms to which those signals propagate, contain an address, chosen for each message by a scheduling PC.
Each mobile transponder has a unique address, and compares this with the address contained in each incoming radio message. If the addresses match, the mobile transponder emits a short pulse of ultrasound, which is detected by a set of receivers (each room has its own receiver set). These receivers include a counter, synchronized with the radio messages by means of a wired network, and it is therefore possible to determine the time-of-flight of the ultrasonic pulse from the mobile transponder to each receiver that detects it.
An estimate of the speed of sound in each room (derived from the ambient temperature) is used to calculate the corresponding transponder-receiver distance.
A non-linear model is then fitted to these distances and the known receiver positions by a regression algorithm which runs on a positioning PC (connected to the receiver set by means of a matrix manager).
A global time signal is sent by a clock generator to the zone manager and matrix manager(s). This signal ensures that the Scheduling PC knows which mobile transponder was triggered in a particular timeslot. It also ensures that, if sufficient ultrasonic signals from that mobile transponder are detected, the positioning PC dealing with the room in which the ultrasonic signals were generated knows where a mobile transponder was at the start of the timeslot.
By correlating these two items of information in a software entity called an area manager, it is possible to determine the 3D position of a mobile transponder at a particular time.
The aforesaid system subject of the above-numbered Patent Applications is later described in more detail.
The system implementation described in the aforesaid Patent Applications has 40 ms timeslots, but these could be shortened to around 20 ms without affecting the basic operation of the system. However, reverberations of an ultrasonic pulse in a typical office may last up to 20 ms, therefore the timeslots cannot be made shorter than this interval. Thus considering the case of a system in which all mobile transponders are in a single room, then with say, a 15 ms timeslot, the period in which reverberations from a mobile transponder triggered in one timeslot might reach a receiver which would overlap the period in which signals from a mobile transponder triggered in the next timeslot might reach the receivers. It would then not be possible to determine which mobile transponder had generated a particular signal, and errors may be introduced into the calculation of a mobile transponder""s location by using a signal generated by another mobile transponder.
When mobile transponders are distributed between a set of rooms, however, the timeslot duration limitation can be unnecessarily restrictive. The periods in which signals from two or more mobile transponders are in flight may overlap safely if it is certain that the signals do not overlap physically. For example, if two mobile transponders are in separate rooms, which are ultrasonically isolated from each other, then the intervals over which their signals are in flight may be overlapped without the possibility of signal cross-contamination. Similarly, in large open-plan offices, the regions in which signals are detected by receivers can be examined, and if those regions are distinct and separated by a significant distance, it can be assumed that the ultrasonic signals will not cross in space.
This consideration appears to suggest that a zone manager could address two or more mobile transponders simultaneously (or as nearly simultaneously as the radio trigger link would allow), as long as those mobile transponders are in separate rooms (or separate ultrasonic spaces).
However, bearing in mind the mobility of the transponders, as the ultrasonic signals contain no addressing information, so a set of signals detected by receivers in an ultrasonic space could have been generated by any of the two or more simultaneously addressed transponders. It would then be impossible to determine which particular mobile transponder was at which location.
Past location information for the mobile transponders might provide some guidance in this matter, but would not rule out the possibility that a number of the mobile transponders had been transposed.
It is therefore necessary to provide some other means by which the area manager can identify which set of detected signals was generated by which mobile transponder.
In our UK Patent Application No 9808526.9 there is provided a system which enables the position of each of a plurality of labelled objects in a specified environment to be determined by determining the transit time of slowly propagating energy transmitted from a transmitter on each labelled object to a plurality of receivers positioned at fixed points in or around the specified environment, and computing therefrom the actual distance of the transmitter from the receivers, wherein the transmission of the slowly propagating energy is initiated by a burst of high speed propagating energy from a master transmitter located so as to cause transmitted bursts of such high speed energy to enter the said environment, the transmitter on the object being controlled by a receiver adapted to respond to an appropriately encoded burst of such high speed energy, each said burst being encoded so that only one of the object mounted receivers is triggered by each burst (each transmitter/receiver combination being referred to as a transponder), to thereby initiate a burst of slowly propagating energy therefrom, wherein the specified environment has at least two zones substantially isolated from one another in respect of the slowly propagating energy, the times at which the transponders are triggered on objects hitherto understood to be in one zone (one set of transponders) are staggered within common timeslots with respect to the times at which the transponders are triggered on objects hitherto understood to be in another zone (another set of transponders), each timeslot being of a sufficient length to enable the receivers to respond to the slowly propagating energy transmitted by the triggered transponders in both the first zone and the or each other zone, and an algorithm is applied to verify the consistency of the transit times of the slowly propagating energy when ascribed to the different sets of transponders.
The slowly propagating energy is typically ultrasound and the high speed energy is radio waves, and in order to be able to distinguish between sets of signals from different mobile transponders, it is first assumed that two different transponders are in different ultrasound zones, the triggering times of those two different mobile transponders (one from each of the two sets) are staggered, and the system is adapted so that receivers are triggered when the first of the said two different mobile transponders is triggered, and the normal 20 ms timeslot is extended by
(mxe2x88x921)xc3x97i,
(where m is the number of mobile transponders triggered in the staggered sequence, and i is the stagger time).
A nonlinear regression calculation used to determine the 3D positions of the mobile transponders should only converge to a solution if it is given a set of consistent transponder-receiver distances and receiver positions. Thus if receiver detected signals are ascribed to the wrong mobile transponder (because it has moved from one zone into another), the pulse times-of-flight calculated for the receiver detected signals will be incorrect, because an inappropriate trigger time will have been used for the signals. The corresponding transponder-receiver distances will then be incorrect, and the nonlinear regression computation will not converge to a solution.
Therefore, given a set of n possible trigger times for mobile transponders, t1, . . . tn, in this method embodying a first check is made to see that the number of sets of signals that were detected in independent ultrasound zones is the same as the number of mobile transponders that were triggered. If this is not so, no further use can be made of these readings, because two or more mobile transponders apparently occupy the same ultrasound zones, in which case signal cross-contamination could have occurred.
Then, for each set of signals s1, . . . , sn, a set of possible corresponding transmitter-receiver distances is calculated for each trigger time, d11, d12, . . . , dnn. By running a nonlinear regression calculation on each set of transmitter-receiver distances (using an algorithm which uses the positions of receivers that detect the corresponding signals), a set of results r11, r12, . . . , rnn is obtained. Each value of rxy, (where 1xe2x89xa6xxe2x89xa6n) and 1xe2x89xa6yxe2x89xa6n is either a 3D position (indicating that the set of signals sx could have been generated by a mobile transponder at time ty) or an error value (indicating that the set of signals sx could not have been generated by a mobile transponder triggered at time ty).
Ideally, one and only one set of signals will be consistent with each trigger time, making it possible to identify which mobile transponder gave rise to those signals (and hence enabling a 3D position to be ascribed to each mobile transponder).
If this is not the case, other heuristics are applied to the results to determine 3D positions for the mobile transmitters. One such heuristic might be that if one set of signals is consistent with two trigger times ta and tb, but another set of signals is consistent with trigger time ta and no other set of signals is consistent with trigger time tb, then the first set of signals was probably generated by a mobile transponder triggered at time tb.
Preferably simulations are performed to validate the heuristics used.
The system enhancement provided by our UK Patent Application No. 9808526.9 is also later described in more detail.
According to the present invention, there is provided a system which enables the position of each of a plurality of labelled objects in a specified environment to be determined by determining the transit time of slowly propagating energy from a transmitter on each labelled object to a plurality of receivers positioned at fixed points within or around the specified environment, and computing therefrom the distances of the transmitter from the receiver, wherein the specified environment is spatially divided into overlapping cells each having a master transmitter for transmitting a burst of high speed propagating energy for detection by object mounted receivers associated with the object mounted transmitters within the compass of the cell, and wherein each cell is allotted an identifying characteristic, the high speed energy transmission by the different master transmitters are multiplexed in accordance with the identifying characteristics of the respective cells, and no two cells having the same identifying characteristic spatially overlap one another.
Typically the slowly propagating energy will be ultrasound energy and the high speed propagating energy will be radio waves.
In general, the transmitter/receiver combinations on each object will hereafter be referred to as transponders, and the master transmitters will be referred to as radio transmitters.
It is clear that the system described in our aforementioned patent application, and which has a single zone manager and associated radio transmitter, cannot be extended to cover an arbitrarily large space, because this would require the radio transmitter to have an arbitrarily large range. In practice, statutory regulations limits the transmitted power output as well as the available frequencies, and hence limit the useful range.
Instead, we must consider a system which has a number of zone managers, each with its own radio transmitter, and each of which is connected to its own scheduling PC.
An overview of this system is given in FIG. 24 of the accompanying drawings. The area around any one of the radio transmitters 300, in which its transmissions can be reliably detected is called a cell. In FIG. 24, five cells are labelled cell 1 to cell 5, respectively. The five cells together cover a larger area.
Zone managers 302 and radio transmitters 300 are placed around the environment such that any point in the large area is covered by at least one cell. Using more transmitters and cells allows even larger areas to be covered, and advantage can be taken of the fact that a combination of smaller cells can have a much higher aggregate location rate than a single large cell.
The cells much be invisible to each other so that transmissions in one cell to not disrupt transmissions in neighbouring cells. This characteristic will be referred to as xe2x80x9corthogonalxe2x80x9dxe2x80x94ie neighbouring cells can be described as being orthogonal. This can be achieved in a number of ways, including time-division multiplexing (TDM), frequency-division multiplexing (FDM) and code-division multiplexing (CDM). Each cell is allocated a colour, which is an identifying characteristic used to distinguish between orthogonal channels in a multiplexing scheme. For example, an FDM system may use four frequencies and each cell is allocated one of the four frequencies and one of four colours indicating which of the four frequencies it uses. When colours are assigned to cells, orthogonality of the cells is ensured by ensuring that no two cells with the same colour overlap at any point in space. Each scheduling PC has a globally unique ID, transmitted as part of messages sent out in its associated cell, which allows mobile transponders to distinguish between cells with the same colour.
All scheduling PCs and positioning PCs are interconnected either by a wired or a wireless network. It is also arranged for each scheduling PC to have its own area manager, with which it can communicate across the network via a CORBA interface. There is therefore a one-to-one mapping from Scheduling PCs (and hence zone managers) to area managers. When the system is configured, measurement of the extents of each cell can be used to determine which zone managers could trigger a mobile transponder in each room (or other ultrasonic space). Each position and orientation determined by a positioning PC is sent to the area manager associated with every zone manager which could trigger a mobile transmitter in that room. Therefore, there is a many-to-many mapping from positioning PCs to area managers.
Where the multiplexing scheme used allows simultaneous transmission of addressing signals in overlapping cells (eg FDM, CDM), some or all colours may use the same timeslots, as shown in FIG. 25 of the accompanying drawings. The global clock signal linking zone managers and matrix managers ensures that each system component knows when a timeslot should begin.
Possible position ambiguities could arise if a number of transmitters are triggered simultaneously in cells which overlap, because the ultrasonic signals emitted by mobile transponders contain no addressing information. By a process of elimination, involving coordination between the scheduling and positioning PCs concerned, it may be possible to use knowledge of which zone managers could trigger a mobile transponder in a particular room to determine which mobile transponder were in which spaces. If insufficient data exists to fully determine which mobile transponders were in which spaces, the ambiguous results must be discarded. We can also use the method of staggered triggering of mobile transponders within extended timeslots, as described in our Patent Application No. 9808526.9 to aid identification of the originators of particular signals and/or to increase the aggregate location rate of such a system.
If the multiplexing scheme does not allow simultaneous transmission of the addressing signals in overlapping cells (eg TDM), timeslots are distributed between colours as shown in FIG. 26 of the accompanying drawings. Again, the global clock signal is used to ensure synchronisation between system components. It is still possible to use the method of staggered triggering of mobile transponders within extended timeslots to increase the aggregate location rate of such a system.
Situations must be considered in which a mobile transponder moves from one cell into another. When this happens, the mobile transponder must perform a xe2x80x9chandoverxe2x80x9d, so that the control of that mobile transponder passes from one scheduling PC to another, and the mobile transponder will begin to receive messages via another cell.
This transfer of control may be passive or active. In an active handover, the mobile transponder, scheduling PC or other monitoring service decides that a transfer of control is appropriate. This may occur because of poor radio link quality, physical position of the mobile transponder, or a desire to share load between cells. If a requirement to transfer control is established, the current scheduling PC sends a message to the mobile transponder indicating that a handover should take place, along with instructions on how to find the new cell. At the same time, a message is sent to the new (provisional) scheduling PC telling it to start addressing the incoming mobile transponder. Both scheduling PCs address the mobile transponder until the provisional scheduling PC detects that the mobile transponder has picked up its addressing signals (see below). At this point the handover is complete and a message is sent to the old scheduling PC telling it to stop addressing the mobile transponder. If the handover requirement changes during this time, the provisional scheduling PC is informed (it then stops addressing the mobile transponder), and (if a handover is still desirable) a new provisional scheduling PC is assigned.
A passive handover occurs when a mobile transponder determines that it has started to receive messages from a new scheduling PC. Examples of situations in which this might occur are:
1. A mobile transponder moves out of a cell quickly. There is no time to perform an active handover, instead, the mobile transponder fails to receive a message over its radio interface, starts to search for another cell, and finds one.
2. A mobile transponder moves quickly from one cell to another which uses the same multiplexing channel. In this case, the mobile transponder does not miss an addressing message, but detects that it has moved to a new cell, because the cell ID in the incoming messages has changed.
3. A sleeping mobile transponder wakes up, searches to find a cell, and finds one.
In all these situations, there is a requirement to indicate to the new scheduling PC that it must start to address the mobile transponder. This can be thought of as a process of registration, by which a mobile transponder registers its existence to a scheduling PC so that it will be included within the list of transponders to be addressed by the PC, as will become clear later.
As mentioned previously, after an active handover it is necessary for the new scheduling PC to be satisfied that the mobile transponder is receiving its messages. It is also necessary that the mobile transponder is satisfied that location resources will be allowed to it. It is therefore proposed that mobile transponders perform the registration process when they lock onto a new cell, and also that the special transmit bit is set in addressing messages (from the new scheduling PC) that are destined for the mobile transponder that is performing the handover. This bit, when set, causes the mobile transponder to immediately transmit its address over the bidirectional radio channel (and prevents other contending mobile transponders from doing so). This is called triggered registration.
There are therefore three ways in which the mobile transponder can tell the scheduling PC that it is receiving its messages; standard registration, triggered registration, and transmission (and subsequent detection) of an ultrasonic pulse generated in response to an addressing message for that mobile transponder.
The registration processes are particularly useful in the case where ultrasonic signals are not being detected because of obstructions, etc.
There are also two ways that the scheduling PC can assure the mobile transponder that location resources have been reserved for it. First, by an addressing message intended to make that mobile transponder send an ultrasonic pulse, and second, by an addressing message containing a separate acknowledgement field, in which the mobile transponder""s unique ID is encoded.